package practice;


import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Day30 {

    //小红取数（动态规划）
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        long[] arr = new long[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextLong();
        }
        long[][] dp = new long[n+1][k];
        for(int i = 1; i < k; i++) {
            dp[0][i] = Long.MIN_VALUE;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < k; j++) {
                dp[i][j] = Math.max(dp[i-1][j],dp[i-1][(int)((j-arr[i-1] % k + k) % k)] + arr[i-1]);
            }
        }
        if(dp[n][0] > 0) {
            System.out.println(dp[n][0]);
        }else {
            System.out.println(-1);
        }
    }

    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.next();
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
            }
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for (Map.Entry entry : map.entrySet()) {
                queue.offer((Integer)entry.getValue());
            }

            int ret = 0;
            while (queue.size() > 1) {
                int t1 = queue.poll();
                int t2 = queue.poll();
                ret += (t1 + t2);
                queue.offer(t1 + t2);
            }
            System.out.println(ret);
        }
    }

    public static void main4(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] arr = in.next().toCharArray();

        Map<Character,Integer> map = new HashMap<>();
        int min = Integer.MAX_VALUE;
        char minC = '0';
        for(char ch : arr) {
            map.put(ch,map.getOrDefault(ch,0) + 1);
            if(min > map.get(ch)) {
                min = map.get(ch);
                minC = ch;
            }
        }

        int sum = 0;
        for(Map.Entry entry : map.entrySet()) {
            char ch = (Character)entry.getKey();
            if(ch != minC) {
                sum += Math.min(Math.abs(ch-'a'),Math.abs(26-(ch-'a')));
            }
        }
        System.out.println(sum);
    }

    //合唱队列（最长子序列）
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = in.nextInt();
        }
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        int max = 0;
        for (int i = 1 ; i <= n; i++) {
            f[i] = 1;
            for (int j = 1; j < i; j++) {
                //从左往右
                if (arr[i] > arr[j]) {
                    f[i] = Math.max(f[i], 1 + f[j]);
                }
            }
        }

        for (int i = n ; i > 0; i--) {
            g[i] = 1;
            for (int j = i + 1; j <= n; j++) {
                //从右往左
                if (arr[i] > arr[j]) {
                    g[i] = Math.max(1 + g[j], g[i]);
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, f[i] + g[i] - 1);
        }
        System.out.println(n - max);

    }

    //过桥（bfs问题）
    private static int[] arr;
    private static int n;
    private static int bfs() {
        int left = 1;
        int right = 1;
        int ret = 0;
        while(left <= right) {
            int r = right;
            ret++;
            for(int i = left; i <= right; i++) {
                r = Math.max(r,arr[i]+i);
                if(r >= n) {
                    return ret;
                }
            }
            left = right+1;
            right = r;

        }
        return -1;
    }
    public static void main5(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        arr = new int[n+1];
        for(int i = 1; i <= n; i++) {
            arr[i] = in.nextInt();
        }
        System.out.println(bfs());
    }
}
